// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-23 23:23
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.DataStruct.Graph.Astart;

import java.util.LinkedList;
import java.util.PriorityQueue;

@SuppressWarnings("ALL")
public class Graph {

    /*-----图中的边类-----*/
    private class Edge {
        // 边的起始节点
        public int sid;
        // 边的结束节点
        public int tid;
        // 边的权重
        public int w;

        public Edge(int s, int t, int w) {
            this.sid = s;
            this.tid = t;
            this.w = w;
        }
    }

    /*-----图中节点类-----*/
    private class Vertex {
        // 顶点编号 ID
        public int id;
        // 从起始顶点，到这个顶点的距离，也就是 g(i)
        public int dist;
        // 新增：f(i)=g(i)+h(i)
        public int f;
        // 新增：顶点在地图中的坐标（x, y）
        public int x, y;

        public Vertex(int id, int x, int y) {
            this.id = id;
            this.x = x;
            this.y = y;
            this.f = Integer.MAX_VALUE;
            this.dist = Integer.MAX_VALUE;
        }
    }

    // 邻接表 -> 链表数组 -> 链表中的元素存储的是边类，数组中存储的信息是链表
    private LinkedList<Edge>[] adj;
    //记录所有顶点的坐标
    private Vertex[] vertexes;
    // 顶点数
    private int v;

    public Graph(int v) {
        this.v = v;
        Vertex[] vertexes = new Vertex[this.v];
        // 图邻接表的大小和图中的节点数量是一致的
        this.adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            this.adj[i] = new LinkedList<Edge>();
        }
    }

    /*
        添加边就是在当前起始节点的邻接表中添加当前的边信息 -> linkedList.add(Edge)
        如果是无向图则一条边需要两次添加操作
     */
    public void addEdge(int s, int t, int w) {
        this.adj[s].add(new Edge(s, t, w));
    }

    //添加顶点坐标
    public void addVetex(int id, int x, int y) {
        vertexes[id] = new Vertex(id, x, y);
    }

    @SuppressWarnings("ALL")
    // 从顶点 s 到顶点 t 的路径
    public void AStar(Graph g, int s, int t) {
        // 用来还原路径,因为会走过所有方向（冯诺依曼领域||摩尔领域）的路径，而且实时记录当前最下路径
        int[] predecessor = new int[this.v];

        // 按照 vertex 的 f 值构建的小顶堆，而不是按照 dist
        /*-----优先队列-----*/
        // 初始化长度为图中节点数量,存储的图中的节点
        PriorityQueue<Vertex> queue = new PriorityQueue<>(this.v);
        // 标记是否已经走过
        boolean[] inqueue = new boolean[this.v];

        // 起始节点初始化
        vertexes[s].dist = 0;
        vertexes[s].f = 0;
        queue.add(vertexes[s]);
        inqueue[s] = true;

        while (!queue.isEmpty()) {
            // 取堆顶元素并删除
            Vertex minVertex = queue.poll();
            for (int i = 0; i < g.adj[minVertex.id].size(); i++) {
                // 从当前节点的邻接链表中取出一条 minVetex 相连的边
                Edge e = g.adj[minVertex.id].get(i);
                // 下一个节点
                Vertex nextVertex = vertexes[e.tid];
                /*-----节点类在初始化的时候dist都被设定为INF-----*/
                // 更新 next 的 dist,f
                if (minVertex.dist + e.w < nextVertex.dist) {
                    // 更新 dist
                    nextVertex.dist = minVertex.dist + e.w;
                    // 更新 f 值
                    nextVertex.f = nextVertex.dist + hManhattan(nextVertex, vertexes[t]);

                    // 记录路径: 当前路径小的时候才记录，而且路径记录是通过记录到达当前节点的最小代价的父节点实现
                    predecessor[nextVertex.id] = minVertex.id;

                    //更新队列中的节点信息 -> 队列中的存在该元素 -> 但是队列中的该元素中的最短路径信息不正确
                    if (inqueue[nextVertex.id] == true) {
                        // queue.update(nextVertex);
                        // 节点还在链表中说明节点及领域节点信息都没被访问
                    } else {
                        queue.add(nextVertex);
                        inqueue[nextVertex.id] = true;
                    }
                }
                // 只要到达终点就退出循环
                if (nextVertex.id == t) {
                    // 清空队列，否则无法退出 while 循环
                    queue.clear();
                    break;
                }
            }
        }
        // 输出路径
        System.out.print(s);
        print(s, t, predecessor);
    }

    /**
     * 计算曼哈顿距离
     */
    int hManhattan(Vertex v1, Vertex v2) {
        return Math.abs(v1.x - v2.x) + Math.abs(v1.y - v2.y);
    }

    private void print(int s, int t, int[] pre) {
        if (s == t) {
            return;
        }
        print(s, pre[t], pre);
        System.out.print("->" + t);
    }

}

